package DifficultPractice;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Demo239 {
//	239. 滑动窗口最大值
//	给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
//	你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
//
//	返回滑动窗口中的最大值。
	
	private class MonotonicQueue{
		private LinkedList<Integer> queue = new LinkedList<>();
		
		public int getMax() {
			return queue.peek();
		}
		
		public void offer(int e) {
			//保证进来的元素都是有序的
			while(!queue.isEmpty() && queue.getLast() < e) {
				queue.removeLast();
			}
			
			queue.addLast(e);
		}
		
		public void poll(int e) {
			if(e == queue.peek()) {
				queue.poll();
			}
		}
	}
	
	public int[] maxSlidingWindow(int[] nums, int k) {
		MonotonicQueue myQueue = new MonotonicQueue();
		LinkedList<Integer> ansList = new LinkedList<>();
		
		for(int i=0; i<nums.length; i++) {
			
			if(i < k-1) {
				//先把前k-1个填充上
				myQueue.offer(nums[i]);
			}
			else {
				myQueue.offer(nums[i]);
				int max = myQueue.getMax();
				myQueue.poll(nums[i - k + 1]);
				ansList.addLast(max);
			}
		}
		
		int[] ans = new int[ansList.size()];
		
		for(int i=0; i<ans.length; i++) {
			ans[i] = ansList.poll();
		}
		
		return ans;
		
    }
	

}
